# 40/100 二叉树-二叉树的直径
# leetcode第101题: https://leetcode.cn/problems/diameter-of-binary-tree/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/11
from typing import Optional
from leetcode.bds import TreeNode
from leetcode.bds import TreeConverter
import leetcode.test as test

"""
二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点。
这题可不是一个简单题!
"""


def diameterOfBinaryTree_dfs(root: Optional[TreeNode]) -> int:
    def dfs(cur: TreeNode):
        """
        深度优先遍历
        :param cur: 当前节点
        :param pl: path nodes nums 途径该节点最大路径的节点数量
        """
        nonlocal res  # 声明 res 来自外围作用域
        if not cur:
            return 0
        l = dfs(cur.left)
        r = dfs(cur.right)
        res = max(res, l + r + 1)  # l + r + 1 表示途径该节点的最长路径
        return max(l, r) + 1

    res = 1
    dfs(root)
    return res - 1


if __name__ == '__main__':
    t1 = TreeConverter.list_to_tree([1, 2, 3, 4, 5])
    t2 = TreeConverter.list_to_tree([2, 1, 3])
    t3 = TreeConverter.list_to_tree([1, 2, 2, None, 3, None, 3])
    t4 = TreeNode(1)
    t5 = TreeConverter.list_to_tree([1, 2, 5, 3, 4, 6, 7, None, 8, None, None, None, None, 0, 9])
    t6 = TreeConverter.list_to_tree(
        [4, -7, -3, None, None, -9, -3, 9, -7, -4, None, 6, None, -6, -6, None, None, 0, 6, 5, None, 9, None, None, -1,
         -4, None, None, None, -2])

    TreeConverter.draw_tree_from_root(t5, figsize=(15, 10))
    inp = [{"root": t1}, {"root": t2}, {"root": t3}, {"root": t4}, {"root": t5}, {"root": t6}, ]
    out = [3, 2, 4, 0, 6, 8]
    test.test_function(diameterOfBinaryTree_dfs, inp, out)
